#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

constexpr int N = 2E5 + 5, M = N * 2, INF = 0x3f3f3f3f;

int h[N], e[M], w[N], ne[M], idx;

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int st[N];

int dist[N];

void dijkstra(int start, int n) {
	memset(dist, 0x3f, sizeof dist);
	priority_queue<PII, vector<PII>, greater<>> heap;
	
	heap.push({0, start});

	while (heap.size()) {
		auto [d, v] = heap.top();	heap.pop();
		if (st[v]) continue;
		st[v] = true;
		cout << v << endl;
		for (int i = h[v]; ~i; i = ne[i]) {
			int j = e[i];
			if (dist[j] > dist[v] + w[i]) {
				dist[j] = dist[v] + w[i];
				heap.push({dist[j], j});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	memset(h, -1, sizeof h);
	int n, m;	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, w;	cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	
	dijkstra(0, n - 1);
	
	for (int i = 0; i < n; ++i) {
		cout << dist[i] << " ";
	}
	
	return 0;
}
